#include<iostream>
#include<vector>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

//void reorderList(ListNode* head) {
//    if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
//        return;
//    ListNode* cur1 = head, * cur2 = head;
//    while (cur2 && cur2->next) {
//        cur1 = cur1->next;
//        cur2 = cur2->next->next;
//    }
//    ListNode* Lhead = cur1->next;
//    cur1->next = nullptr;
//    ListNode* Phead = new ListNode(0);
//    while (Lhead) {
//        ListNode* next = Lhead->next;
//        Lhead->next = Phead->next;
//        Phead->next = Lhead;
//        Lhead = next;
//    }
//    ListNode* sum = new ListNode(0), * ccur1 = head, * ccur2 = Phead->next;
//    ListNode* hhead = sum;
//    while (ccur1) {
//        sum->next = ccur1;
//        ccur1 = ccur1->next;
//        sum = sum->next;
//        if (ccur2) {
//            sum->next = ccur2;
//            ccur2 = ccur2->next;
//            sum = sum->next;
//        }
//    }
//    head = hhead->next;
//    while (head)
//    {
//        cout << head->val << " ";
//        head = head->next;
//    }
//    delete sum;
//    delete Phead;
//}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    Mergelist(lists, 0, lists.size() - 1);
    return lists[0];
}
void Mergelist(vector<ListNode*>& lists, int left, int right)
{
    if (left >= right) return;
    int mid = left + (right - left) >> 1;
    Mergelist(lists, left, mid);
    Mergelist(lists, mid + 1, right);
    ListNode* cur1 = lists[left], * cur2 = lists[mid + 1];
    ListNode* Lhead = new ListNode(0);
    ListNode* sum = Lhead;
    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            Lhead->next = cur1;
            cur1 = cur1->next;
            Lhead = Lhead->next;
        }
        else
        {
            Lhead->next = cur2;
            cur2 = cur2->next;
            Lhead = Lhead->next;
        }
    }
    if (cur1)
        Lhead->next = cur1;
    if (cur2)
        Lhead->next = cur2;
    lists[left] = sum->next;
}
int main()
{
    //ListNode* head = new ListNode(1);
    //head->next = new ListNode(2);
    //head->next->next = new ListNode(3);
    //reorderList(head);

    return 0;
}